1. Field of the Invention
The present invention relates to the field of networking, specifically to the field of routing messages in the network. More specifically, the present invention relates to methods and apparatus providing for management of exchange of metrics between routing nodes in the network.
2. Description of the Related Art
Communications networks allow multiple user nodes (also known as hosts or end systems, i.e., computers, file servers, etc.) to communicate often via one or more intermediate node (e.g., a router or a switch). In general, the user nodes may be interconnected via a relatively complex topology of intermediate nodes. It is therefore necessary to make use of a routing protocol in order to compute paths through the network from a source user node to a destination user node via one or more intermediate nodes.
Advertising and utilization of metrics
Routing protocols frequently need to select one path to a given destination out of a set of multiple possible paths. Typically, this is done based on a set of characteristic elements which make up the path. Such characteristics are known as metrics.
Certain routing protocols, such as the well-known Routing Information Protocol (RIP) select a path based on one characteristic (e.g., hop count), while others allow use of multiple characteristics, e.g., OSPF (see, J. Moy, Network Working Group, RFC 1247, July, 1991).
Recently, advances in networking have increased the need for more advanced path selection based on additional metrics. For example, quality of service (QOS) routing may be utilized to minimize one characteristic (for example total cost), subject to multiple constraints (for example, total path delay must be less than a specified value, available bandwidth for each element in the path must be greater than a specified value, etc.) This type of calculation requires that the routing computation have available a variety of metrics describing the characteristics of nodes and links along the path. The variety of routing computations which can be utilized to implement QOS is enormous and it is difficult to predict in advance which metrics will be required for the computations in any given network.
FIG. 1 illustrates a simple example network including nodes A-G. In order to perform advanced QOS routing in this network each node A-G may advertise a complex set of metrics describing its capabilities and current loading as well as the capabilities and current loading of its links. These advertisements are flooded to all other nodes in the network. Thus, each node, in selecting a path to other nodes, may consider the characteristics and load of every other element in the network.
Unfortunately, if each node advertises all of its available metrics, even in a relatively simple network the number of metrics which must be periodically advertised may be high which in turn adds significant network overhead. For example, in the simple exemplary network of FIG. 1, if each of the 7 nodes each advertised only 3 metrics, 21 metric advertisements would need to be advertised on the network. Of course, in present day QOS networks, the number of metrics available for advertisement may be considerably larger than 3 and the number of nodes in a typical network may be considerably increased over the simple example of FIG. 1.
Importantly even while the number of metrics which may be available for advertisement is large, it is not predictable in advance which metrics will be required by the various nodes in the network.
As will be discussed in greater detail below, the present invention recognizes both of these issues--i.e., the relatively large amount of network traffic which is generated by all nodes advertises all of their available metrics and the unpredictability of the which metrics will be required--and the present invention implements a solution which allows for advertising of only those metrics which are required, thereby significantly reducing network overhead and required storage space on the various nodes for metrics.
Hierarchical Routing
FIG. 1 illustrates a simple, flat network architecture. Many existing network architectures allow for hierarchical routing. A hierarchical network is illustrated with reference to FIG. 2. In the network of FIG. 2, each node in group Y exchanges complete information (including a set of metrics) with all other nodes in group Y. From outside of group Y however, the entire group is summarized as a single node (illustrated graphically as node "Y" at the top of the figure). In order to implement quality of service routing, the summary nodes (such as nodes X, Y and Z) must advertise a complex set of metrics describing the capabilities and current load on the summary node. The number of metrics which are available for advertisement is equal to the total number of different metrics advertised by each individual node in group Y. Thus, the number of available metrics can be quite large.
Link State advertisements
It is worthwhile to briefly mention the use of link state advertisement in routing protocols. Link state advertisements are advertised by each node in the network over each of their active links in order to provide other nodes in the network with information indicating that an active node exists. FIG. 3 is a high level illustration of a simple flat network showing advertisement of link state on the various links. The link state advertisements are advertised periodically by each node in the network, and each link state advertisement is flooded to each node in the network.
To summarize, as stated above, the amount of metric information which may be required to be advertised in a network is potentially quite large and, as a result, the overhead associated with advertising and storing of the metric information is potentially correspondingly large. Therefore, it is desired to develop methods for minimizing network overhead when sharing metric information in a network.